[Overview] [Previous] [Next]

The Pigeonhole Principle

pigeonhole: (pij' un hole) n

a hole or small recess for pigeons to nest
a small open compartment (as in a desk or cabinet) for keeping letters or documents
a neat category which usu. fails to reflect actual complexities.

pigeonhole principle: if n objects are put into m containers, where n > m, then at least one container must hold more than one object.

The pigeonhole principle can be used to prove that certain infinite languages are not regular. (Remember, any finite language is regular.)

As we have informally observed, dfas "can't count." This can be shown formally by using the pigeonhole principle. As an example, we show that L = {a n times b n times : n > 0} is not regular. The proof is by contradiction.

Suppose L is regular. There are an infinite number of values of n but M(L) has only a finite number of states. By the pigeonhole principle, there must be distinct values of i and j such that aⁱ and a^j end in the same state. From this state,

bⁱ must end in a final state, because aⁱbⁱ is in L; and
bⁱ must end in a nonfinal state, because a^jbⁱ is not in L.

Since the state reached cannot be both final and nonfinal, we have a contradiction. Thus our assumption, that L is regular, must be incorrect. Q.E.D.